﻿package com.gamemeal.geom {
	import flash.geom.Point;
	/**
	 * @author Colin
	 */
	public class KNearestNeighbor {
		private var PROJX:Number;
		private var PROJY:Number;
	
		private var n : Number;// This is the number of point expected to be tested
		private var projaxe:Number;// Current projection axe
		private var compare:Number;// Number of compare made to find the nearest
		private var maxradius:Number;// Maximum radius of search in the array
		private var ndata:Number;// Number of data in the arrays
		private var dataPt:Array;// Point array
		private var xindex:Array;// Index for coordinates X (x is the index, y is the value)
		private var yindex : Array;// Index for coordinates Y (x is the index, y is the value)
		private var flags : Array;// Array of flags that indicate the validity of point (true or false)
	
		private var cindex : Array;// Pointer to current index
		private var cvalue : Number;// Current values for the search
	
		private var cind : Number;
		private var cp : Point;// Current point being tested
		private var kn : Number;
		private var points : Array;
		
		public function KNearestNeighbor(points:Array){
		    // Projection axes defines
		    this.PROJX = 1;
		    this.PROJY = 2;
		
			this.points = points;
		
			this.n = 20; // We expect to test 10 points... (this is arbitrary)
			// Copy the point vector into an array
			this.ndata = points.length;
			// We create the arrays
			this.dataPt = [];
			this.xindex = [];
			this.yindex = [];
			this.flags = [];
			// We initialise the data
			for(var i:int=0; i < this.ndata; i++)
			{
				this.dataPt[i] = Point(points[i]);
				//trace(this.dataPt[i].x);
				// Create a new point which will have
				// field x : the index of the original point in the array (data)
				// field y : the value of the projected point on the axe
				this.xindex[i] = new PointObj(i, this.dataPt[i].x);
				this.yindex[i] = new PointObj(i, this.dataPt[i].y);
				this.flags[i] = true;    // The point is valid
			}
			// Sort the index for axe X
//			this.cindex = this.xindex;
//			this.bubbleSort();
			// Sort the index for axe Y
			this.cindex = this.yindex;
			this.bubbleSort();

			this.compare = 0;
		}
	
		private function bubbleSort():void{
			//trace(this.cindex[1].y);
			var ptmp:PointObj;
			for (var i:int = this.ndata-1; i >= 0; i--)
			{
				for (var j:int = 0; j<i; j++)
				{
					if (this.cindex[j].y > this.cindex[j+1].y)
					{   // Swap the points
						ptmp = this.cindex[j];
						this.cindex[j] = this.cindex[j+1];
						this.cindex[j+1] = ptmp;
					}
				}
			}
		}
		
		public function getCompare():Number{
			return this.compare;
		}
		
		public function getMaxRadius():Number{
			return this.maxradius;
		}
		
		public function getProjectionAxe():Number{
			return this.projaxe;
		}
		
		public function dichoSearchIndex(value:Number):Number{
			//trace(value)
			var inf:Number, sup:Number, centre:Number;
			inf = 0;
			sup = this.ndata-1;
		
			// Check for obious case
			if(value <= this.cindex[inf].y) return inf;
			else if(value >= this.cindex[sup].y) return sup;
		
			// Search until we have at least two elements
			while(sup > inf)
			{
				centre = int((inf+sup)/2);
				if(this.cindex[centre].y == value) return centre;
				else if(this.cindex[centre].y < value) inf = centre+1;
				else sup = centre-1;
			}
			return inf;
		}
		
		public function resetFlags() :void{
			for(var i:int=0; i < this.ndata; i++) this.flags[i] = true;
		}
		
		public function setKN(k:Number):void{
			if(k > 0 && k < this.points.size()) this.kn = k;
		}
		
		public function getKN():Number{
			return this.kn;
		}
		
		public function findFirstNN(p:Point):Point{
			var index1:int, index2:int, i:int,j:int;
			var sparse1:Number, sparse2:Number;
			var xdim:Number, ydim:Number;
			var s1:Number,s2:Number;
			// Compute the dimension of the pointset
			xdim = this.xindex[this.ndata-1].y - this.xindex[0].y;
			ydim = this.yindex[this.ndata-1].y - this.yindex[0].y;
		
			// Remember the point being tested
			this.cp = p;
		
			// Reset the flags
			this.resetFlags();
		
			// Find the point on the projected axes
			this.cindex = this.xindex;
			//trace(p.x)
			index1 = this.dichoSearchIndex(p.x);
			this.cindex = this.yindex;
			//trace(p.y)
			index2 = this.dichoSearchIndex(p.y);
		
		
			//trace("***")
			//trace(index1)
			//trace(index2)
			//trace("***")
		
			// Mesure the sparsity of axe X
			i = int(index1 - this.n/2);
			if(i < 0) i = 0;
			j = int(index1 + this.n/2);
			if(j >= this.ndata) j = this.ndata-1;
			sparse1 = this.xindex[j].y - this.xindex[i].y;
			// Normalize sparsity
			s1 = int(sparse1/xdim);
		
			// Mesure the sparsity of axe Y
			i = int(index2 - this.n/2);
			if(i < 0) i = 0;
			j = int(index2 + this.n/2);
			if(j >= this.ndata) j = this.ndata-1;
			sparse2 = this.yindex[j].y - this.yindex[i].y;
			// Normalise sparsity
			s2 = int(sparse2/ydim);
		
			if(s1 > s2)
			{   // We take the x axe
				this.cindex = this.xindex;
				this.cvalue = p.x;
				this.cind = index1;
				this.projaxe = this.PROJX;
			}
			else
			{   // We take the y axe
				this.cindex = this.yindex;
				this.cvalue = p.y;
				this.cind = index2;
				this.projaxe = this.PROJY;
			}
		
			// Init the number of compare
			this.compare = 0;
			this.maxradius = 0;
			return this.findNextNN();
		}
		
		public function findNextNN():Point {
			var mindist:Number,dist:Number;
			var mini:Number;
			var i:int, il:int, ir:int;
		
			// Find the radius of the circle
			// cind is already at the left of the test point
			il = this.cind;
			// Find the closest next valid point
			while(this.flags[this.cindex[il].x] == false && il > 0) il--;
			if(this.flags[this.cindex[il].x] == true)
			{
				// Compute the distance
				mindist = this.computeDistance(this.cp, this.dataPt[this.cindex[il].x]);
				this.compare++;
			}
			else
				// Put something big no chance of having a distance bigger than that
				mindist = 500*500;
		
			// Here, we must verify if it's not the end already
			if(this.cind < this.ndata-1)
			{
				ir = this.cind+1;
				while(this.flags[this.cindex[ir].x] == false && ir < this.ndata-1) ir++;
				if(this.flags[this.cindex[ir].x] == true)
				{
					dist = this.computeDistance(this.cp, this.dataPt[this.cindex[ir].x]);
					this.compare++;
				}
				else dist = 500*500;
		
				if(mindist < dist)
				{
					this.maxradius = Math.sqrt(mindist);
					mini = il;
				}
				else
				{
					mini = ir;
					this.maxradius = Math.sqrt(dist);
					mindist = dist;
				}
			}
			else
			{
				mini = il;
				ir = this.ndata-1;
				this.maxradius = Math.sqrt(mindist);
			}
		
		
			// Search to the left of cind
			i = il-1;
			while(i > 0 && this.maxradius > Math.abs(this.cvalue-this.cindex[i].y))
			{
				if(this.flags[this.cindex[i].x] == true)
				{
					dist = computeDistance(this.cp, this.dataPt[this.cindex[i].x]);
					this.compare++;
					if(dist < mindist)
					{
						mindist = dist;
						mini=i;
					}
				}
				// Go to the left
				i--;
			}
		
			// Search to the right of cind
			i = ir+1;
			while(i < this.ndata && this.maxradius > Math.abs(this.cindex[i].y - this.cvalue))
			{
				if(this.flags[this.cindex[i].x] == true)
				{
					dist = this.computeDistance(this.cp, this.dataPt[this.cindex[i].x]);
					this.compare++;
					if(dist < mindist)
					{
						mindist = dist;
						mini=i;
					}
				}
				i++; // Go to the right
			}
		
			// Set the flag of the point found to false so that
			// we don't find it again for next search
			this.flags[this.cindex[mini].x] = false;
		
			// return the closest point
			return this.dataPt[this.cindex[mini].x];
		}
		
		public function findNearestNeighborCrude( p:Point ):Point{
			var mindist:Number,dist:Number;
			var mini:Number = 0;
			// Init compare
			this.compare = 0;
			mindist = this.computeDistance(p, this.dataPt[mini]);
			for(var i:int=0; i < this.ndata; i++)
			{
				dist = this.computeDistance(p, this.dataPt[i]);
				this.compare++;
				if(dist < mindist)
				{
					mini = i;
					mindist = dist;
				}
			}
			return this.dataPt[mini];
		}
		
		public function computeDistance(p1:Point, p2:Point):Number{
			var dx:Number = p2.x - p1.x;
			var dy:Number = p2.y - p1.y;
			return (dx*dx + dy*dy);
		}
	}
}

final class PointObj{
	public var x:Number;
	public var y:Number;
	public function PointObj(x:Number,y:Number){
		this.x = x;
		this.y = y;
	}
}